1818E - Similar Polynomials - CodeForces Solution

#include <bits/stdc++.h>
typedef long long i64;
#define F(x, y, z) for (int x = (y); x <= (z); ++x)
#define DF(x, y, z) for (int x = (y); x >= (z); --x)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pii pair<int, int>
#define mp make_pair
#define mem(x, y) memset(x, y, sizeof(x))
#define vi vector<int>
#define vi64 vector<i64>
using namespace std;
int read() {
	char ch = getchar();
	int x = 0, pd = 0;
	while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
	return pd ? -x : x;
}
const int maxn = 2500000;
namespace modular {
const int mod = 1000000007;
int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
int dec(int x, int y) { return add(x, mod - y); }
int mul(int x, int y) { return 1ll * x * y % mod; }
int Pow(int x, int y) {
	int res = 1;
	for (; y; y >>= 1, x = mul(x, x))
		if (y & 1) res = mul(res, x);
	return res;
}
int fac[maxn], invf[maxn];
void init(int N) {
	fac[0] = 1;
	for (int i = 1; i <= N; i++) fac[i] = mul(fac[i - 1], i);
	invf[N] = Pow(fac[N], mod - 2);
	for (int i = N - 1; i >= 0; i--) invf[i] = mul(invf[i + 1], i + 1);
}
int C(int N, int M) { return N < M ? 0 : mul(fac[N], mul(invf[M], invf[N - M])); }
} using namespace modular;
int main() {
	int n = read();
	init(n);
	int A = 0, t = 1, k = read();
	F(i, 1, n) {
		int x = read();
		A = add(A, mul(t, mul(C(n - 1, i - 1), x)));
		t = mod - t;
		if (i < n) k = add(k, mul(t, mul(C(n - 1, i), x)));
	}
	k = dec(A, k);
	int tmp = read(); t = 1;
	F(i, 1, n) {
		int x = read();
		A = dec(A, mul(t, mul(C(n - 1, i - 1), x)));
		t = mod - t;
	}
	printf("%d\n", mul(add(0, mod - A), Pow(k, mod - 2)));
	return 0;
}